P (複雜度)

在計算複雜度理論中，P（polynomial time class）是在複雜度類別問題中可於確定型圖靈機以多項式量級（或稱多項式時間）求解的決定性問題。

複雜度關係韋恩圖

P通常表示那類可以「有效率地解決」或「溫馴」的可計算型問題，就算指數級非常高也可以算作「溫馴」，例如RP與BPP問題。當然P類別存在很多現實處理上一點也不溫馴的問題，例如一些至少需要n^1000000指令來解決的問題。很多情況下存在着更難的複雜度問題

在P中令人注目的問題

P包含了很多已知的自然問題，例如決定性版本的線性規劃，計算最大公因數，以及發現最大匹配。在2002年，判別一個數是否為質數也被人解出是一個P問題^[1]。與功能性問題相關的類別是FP。

與其他類別的關係

P的擴大集合是NP，此複雜度類別是一個可在多項式時間以非確定型圖靈機決定答案的問題的集合。因此我們可知道P是NP的子集，且雖然未證明，但大部分專家相信P是NP的嚴格子集（即NP一定大於且包含P集合）。^[2]

P也已知至少大於L一個可在對數量級的記憶體空間上決定的問題的類別。一個判定演算法使用了O(log n)的空間就不可能使用超過2^{O(log n)}=n^O(1)的時間，因為這是所有可能組合方式的總數，因此L是P的子集合。另一個重要問題是：L是否相等於P？我們已知P=AL（問題可在對數記憶體上以交替式圖靈機解決的問題之集合），而P也已知不大於PSPACE（可在多項式空間判定的問題）。再一次，我們面對P是否等於PSPACE的未知問題。整理一下上述問題：

${\displaystyle {\mbox{L}}\subseteq {\mbox{AL}}={\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PSPACE}}\subseteq {\mbox{EXPTIME}}}$

EXPTIME指的是可在指數時間解答的問題類別。在上列的類別關係中，只有兩個嚴格包含關係是確定的：

• P嚴格包含於EXPTIME之中。因此所有EXPTIME-hard問題在P集合之外，且最少一個P右方的包含關係是嚴格的（事實上，大部分人認為P右邊三個集合都是嚴格包含P）。
• L嚴格包含於PSPACE集合中。

在P問題中最困難的是P-完全問題。

另一個P的擴大集合是P/poly，或非統一多項式時間。若一個問題落於P\poly，則它可以在依據輸入內容的長度下給予提示字串（advice string）的情況下，以確定性多項式時間解決。然而，不像NP，此多項式時間機器不需要偵測偽造提示字串；因為它不是一個驗證機器。P/poly是一個幾乎包含所有實際演算法的巨大類別，包含所有BPP。如果P/poly包含了NP，則整個多項式譜系將會下降到第二階層。另一方面，它也包含一些不切實際的演算法，包含一些可決定問題，例如一元版的任何非決定性問題。

性質

多項式時間演算法擁有組裝封閉性。換句話說，若我寫了一個內容是多項式時間的函數（若視函數呼叫為固定時間），且其它被本函數呼叫的副函數也屬於多項式時間，則整個組合起來的演算法也會是多項式時間。因此P是自我低陷的，這也是P被認為是無關機器類型的主要理由：任何機器特徵（例如隨機存取）可以用多項式時間演算法模仿的話，可在一些更簡單的機器以其他多項式時間演算法組合並化約而成，且時間複雜度依然是P。

歷史

Kozen^[3]指出Cobham與Edmonds是最可信，最早創造多項式時間這個名詞的人。

註釋

1. Manindra Agrawal, Neeraj Kayal, Nitin Saxena, "PRIMES is in P （頁面存檔備份，存於互聯網檔案館）", Annals of Mathematics 160 (2004), no. 2, pp. 781–793.
2. Johnsonbaugh, Richard; Schaefer, Marcus, Algorithms, 2004 Pearson Education, page 458, ISBN 978-0-02-360692-2
3. Kozen, Dexter C. Theory of Computation. Springer. 2006: 4. ISBN 978-1-84628-297-3.

參考資料

• C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994. ISBN 978-0-201-53082-7.
• Complexity Zoo: P，P/poly
• Thomas H. Cormen，Charles E. Leiserson，Ronald L. Rivest，and Clifford Stein。Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 978-0-262-03293-3. Section 34.1: Polynomial time, pp.971–979.
• Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 978-0-534-94728-6. Section 7.2: The Class P, pp.234–241.